//
// Created by liushuai on 2021/1/26.
//

#include "reverseKGroup.h"

ListNode *reverseKGroup(ListNode *head, int k) {
  int length = linkLength(head);
  if (length < k) return head;
  int seg = length / k;
  ListNode *currentNode = head;
  ListNode *nextNode;
  ListNode *segTail = nullptr;
  ListNode *newHead = nullptr;

  for (int i = 0; i < seg; i++) {
    ListNode *preNode = nullptr;
    for (int j = 0; j < k; j++) {
      nextNode = currentNode->next;
      currentNode->next = preNode;
      preNode = currentNode;
      currentNode = nextNode;
    }  // 每一段转换为a->b->null
    if (!segTail) {
      newHead = preNode;  // 设置新链表头
      ListNode *temp = preNode;
      while (temp && temp->next) {
        temp = temp->next;  // 找到段的最后一个元素作为段连接下一段的元素
      }
      segTail = temp;

    } else {
      segTail->next = preNode;
      ListNode *temp = preNode;
      while (temp && temp->next) {
        temp = temp->next;
      }
      temp->next = segTail;
      segTail = temp;
    }
  }
  segTail->next = currentNode;
  return newHead;
}
